package com.hsoft.zhxy.common.util;

/***
 * KMP算法 快速比对两个字符串之间是否包含
 * @author mlingwei 2016
 */
public class KMPUtils {

    /**
     * 判断是否匹配
     * @param target 目标文本串
     * @param mode   模式串(传入参数)
     * @return 匹配结果
     */
    public static boolean matchString(String target, String mode) {

        String newTarget = "x" + target;
        String newMode = 'x' + mode;

        int[] K = calculateK(mode);

        int i = 1;
        int j = 1;
        while (i <= target.length() && j <= mode.length()) {
            if (j == 0 || newTarget.charAt(i) == newMode.charAt(j)) {
                i++;
                j++;
            } else {
                j = K[j];
            }
        }

        if (j > mode.length()) {
            return true;
        }
        return false;
    }

    private static int[] calculateK(String mode) {

        String newMode = "x" + mode;
        int[] K = new int[newMode.length()];
        int i = 1;
        K[1] = 0;
        int j = 0;

        while (i < mode.length()) {
            if (j == 0 || newMode.charAt(i) == newMode.charAt(j)) {
                i++;
                j++;
                K[i] = j;
            } else {
                j = K[j];
            }
        }

        return K;
    }

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        String a = "中华人民共和国";
        String b = "人民";// "ababbaaba";//
        System.out.println(KMPUtils.matchString(a, b));
    }

}